package 代码随想录_贪心算法;

import java.util.*;

public class 根据身高重建队列_406 {
    public static int[][] reconstructQueue(int[][] people) {
        // 身高从大到小排（身高相同k小的站前面）
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] person1, int[] person2) {
                if(person1[0] == person2[0]){
                    return person1[1] - person2[1];//K代表第二个维度
                }else{
                    return person2[0] - person1[0];//身高从大到小排列
                }
            }
        });

        LinkedList<int[]> queue = new LinkedList<>();

        for (int[] person : people) {
            queue.add(person[1],person);
        }
        int[][] res = new int[people.length][];
        int length = queue.size();
        for (int i = 0;i < length;i++){
            res[i] = queue.pollFirst();
        }
        return res;
    }
    /**
    回归本题，整个插入过程如下：
    排序完的people：[[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]
    插入的过程：
        插入[7,0]：[[7,0]]
        插入[7,1]：[[7,0],[7,1]]
        插入[6,1]：[[7,0],[6,1],[7,1]]
        插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
        插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
        插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
        此时就按照题目的要求完成了重新排列。
     */
}
